package cc.wsyw126.java.lintCode;

/**
 * Created by Administrator on 2017/4/13.
 */
public class VerifySquenceOfBST {
    public boolean VerifySquenceOfBST(int[] sequence) {
        int length = sequence.length;
        return doVerifySquenceOfBST(sequence, 0, length - 1);

    }

    public boolean doVerifySquenceOfBST(int[] sequence, int low, int high) {
        if (low > high) return false;
        if (low == high) return true;
        int root = sequence[high];
        int i = low;
        for (; i <= high - 1; i++) {
            if (sequence[i] > root) {
                break;
            }
        }
        int j = i;
        for (; j <= high - 1; j++) {
            if (sequence[j] < root) {
                return false;
            }
        }
        boolean left = true;
        if (i - 1 > low) {
            left = doVerifySquenceOfBST(sequence, low, i - 1);
        }
        boolean right = true;
        if (i < high - 1) {
            right = doVerifySquenceOfBST(sequence, i, high - 1);
        }
        return left && right;
    }

    public static void main(String[] args) {
        VerifySquenceOfBST verifySquenceOfBST = new VerifySquenceOfBST();
        int[] s = {5, 7, 6, 9, 11, 10, 8};
        boolean b = verifySquenceOfBST.VerifySquenceOfBST(s);
        System.out.println(b);
    }
}
